{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Remove Stones to Minimize the Total"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minStoneSum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #移除石子使总数最小"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>piles</code> ，数组 <strong>下标从 0 开始</strong> ，其中 <code>piles[i]</code> 表示第 <code>i</code> 堆石子中的石子数量。另给你一个整数 <code>k</code> ，请你执行下述操作 <strong>恰好</strong> <code>k</code> 次：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>选出任一石子堆 <code>piles[i]</code> ，并从中 <strong>移除</strong> <code>floor(piles[i] / 2)</code> 颗石子。</li>\n",
    "</ul>\n",
    "\n",
    "<p><strong>注意：</strong>你可以对 <strong>同一堆</strong> 石子多次执行此操作。</p>\n",
    "\n",
    "<p>返回执行 <code>k</code> 次操作后，剩下石子的 <strong>最小</strong> 总数。</p>\n",
    "\n",
    "<p><code>floor(x)</code> 为 <strong>小于</strong> 或 <strong>等于</strong> <code>x</code> 的 <strong>最大</strong> 整数。（即，对 <code>x</code> 向下取整）。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>piles = [5,4,9], k = 2\n",
    "<strong>输出：</strong>12\n",
    "<strong>解释：</strong>可能的执行情景如下：\n",
    "- 对第 2 堆石子执行移除操作，石子分布情况变成 [5,4,<strong><em>5</em></strong>] 。\n",
    "- 对第 0 堆石子执行移除操作，石子分布情况变成 [<strong><em>3</em></strong>,4,5] 。\n",
    "剩下石子的总数为 12 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>piles = [4,3,6,7], k = 3\n",
    "<strong>输出：</strong>12\n",
    "<strong>解释：</strong>可能的执行情景如下：\n",
    "- 对第 2 堆石子执行移除操作，石子分布情况变成 [4,3,<strong><em>3</em></strong>,7] 。\n",
    "- 对第 3 堆石子执行移除操作，石子分布情况变成 [4,3,3,<strong><em>4</em></strong>] 。\n",
    "- 对第 0 堆石子执行移除操作，石子分布情况变成 [<strong><em>2</em></strong>,3,3,4] 。\n",
    "剩下石子的总数为 12 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= piles.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= piles[i] &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [remove-stones-to-minimize-the-total](https://leetcode.cn/problems/remove-stones-to-minimize-the-total/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [remove-stones-to-minimize-the-total](https://leetcode.cn/problems/remove-stones-to-minimize-the-total/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[5,4,9]\\n2', '[4,3,6,7]\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStoneSum(self, piles: List[int], k: int) -> int:\n",
    "        def fixHeap(idx):\n",
    "            while idx < int(len(piles) / 2):\n",
    "                child = idx*2 + 1\n",
    "                if child + 1 < len(piles) and piles[child+1] > piles[child]:\n",
    "                    child = child+1\n",
    "                if piles[idx] >= piles[child]:\n",
    "                    return\n",
    "                piles[idx], piles[child] = piles[child], piles[idx]\n",
    "                idx = child\n",
    "\n",
    "\n",
    "        def initHeap():\n",
    "            for i in range(int(len(piles) / 2) - 1, -1, -1):\n",
    "                fixHeap(i)\n",
    "\n",
    "        initHeap()\n",
    "        while k > 0:\n",
    "            half = math.floor(piles[0]/2)\n",
    "            piles[0] -= half\n",
    "            fixHeap(0)\n",
    "            k -= 1\n",
    "        return sum(piles)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStoneSum(self, piles: List[int], k: int) -> int:\n",
    "        def fixHeap(idx):\n",
    "            while idx < int(len(piles) / 2):\n",
    "                child = idx*2 + 1\n",
    "                if child + 1 < len(piles) and piles[child+1] > piles[child]:\n",
    "                    child = child+1\n",
    "                if piles[idx] > piles[child]:\n",
    "                    return\n",
    "                piles[idx], piles[child] = piles[child], piles[idx]\n",
    "                idx = child\n",
    "\n",
    "\n",
    "        def initHeap():\n",
    "            for i in range(int(len(piles) / 2) - 1, -1, -1):\n",
    "                fixHeap(i)\n",
    "\n",
    "        initHeap()\n",
    "        while k > 0:\n",
    "            half = math.floor(piles[0]/2)\n",
    "            piles[0] -= half\n",
    "            fixHeap(0)\n",
    "            k -= 1\n",
    "        return sum(piles)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStoneSum(self, piles: List[int], k: int) -> int:\n",
    "        def fixHeap(idx):\n",
    "            while idx < int(len(piles) / 2):\n",
    "                child = idx*2 + 1\n",
    "                if child + 1 < len(piles) and piles[child+1] > piles[child]:\n",
    "                    child = child+1\n",
    "                if piles[idx] > piles[child]:\n",
    "                    return\n",
    "                piles[idx], piles[child] = piles[child], piles[idx]\n",
    "                idx = child\n",
    "\n",
    "\n",
    "        def initHeap():\n",
    "            for i in range(int(len(piles) / 2) - 1, -1, -1):\n",
    "                fixHeap(i)\n",
    "\n",
    "        initHeap()\n",
    "        while k > 0:\n",
    "            half = math.floor(piles[0]/2)\n",
    "            piles[0] -= half\n",
    "            fixHeap(0)\n",
    "            k -= 1\n",
    "        return sum(piles)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStoneSum(self, piles: List[int], k: int) -> int:\n",
    "        ans = sum(piles)\n",
    "        h = []\n",
    "        for p in piles: heappush(h, -p)\n",
    "        for _ in range(k):\n",
    "            t = heappop(h)\n",
    "            t = -t\n",
    "            ans -= t // 2\n",
    "            heappush(h, -(t - t // 2))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStoneSum(self, piles: List[int], k: int) -> int:\n",
    "        n = len(piles)\n",
    "        for i in range(n):\n",
    "            piles[i] = -piles[i]\n",
    "        heapify(piles)\n",
    "\n",
    "        for i in range(k):\n",
    "            tmp = heappop(piles)\n",
    "            heappush(piles, tmp//2)\n",
    "        return -sum(piles)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \"\"\"\n",
    "        n = len(piles)\n",
    "        # 生成最大堆\n",
    "        for i in range(n):\n",
    "            piles[i] = -piles[i]\n",
    "        heapq.heapify(piles)\n",
    "        for i in range(k):\n",
    "            # 单次操作：记录并弹出最大值，修改后重新添加进堆\n",
    "            tmp = heapq.heappop(piles)\n",
    "            heapq.heappush(piles, tmp // 2)\n",
    "        return -sum(piles)\n",
    "        \"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStoneSum(self, piles: List[int], k: int) -> int:\n",
    "        h=[]\n",
    "        import heapq\n",
    "        for x in piles:\n",
    "            heapq.heappush(h,-x)\n",
    "        for i in range(k):\n",
    "            n=-heapq.heappop(h)\n",
    "            heapq.heappush(h,-(n-floor(n/2)))\n",
    "        return -sum(h)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStoneSum(self, piles: List[int], k: int) -> int:\n",
    "        for i in range(len(piles)):\n",
    "            piles[i]=-piles[i]\n",
    "        heapq.heapify(piles)\n",
    "        for i in range(k):\n",
    "            a=heapq.heappop(piles)\n",
    "            b=int(-a//2)\n",
    "            c=a+b\n",
    "            heapq.heappush(piles,c)\n",
    "        return -sum(piles)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStoneSum(self, piles: List[int], k: int) -> int:\n",
    "        for i in range(len(piles)):\n",
    "            piles[i] *= -1\n",
    "        heapify(piles)\n",
    "        for i in range(k):\n",
    "            heapreplace(piles,piles[0]//2)\n",
    "        return -sum(piles)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStoneSum(self, piles: List[int], k: int) -> int:\n",
    "        pq = [-x for x in piles]\n",
    "        heapify(pq)\n",
    "        while k > 0 and -pq[0] > 0:\n",
    "            k -= 1\n",
    "            heapreplace(pq, -ceil(-pq[0] / 2))\n",
    "        return -sum(pq)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStoneSum(self, piles: List[int], k: int) -> int:\n",
    "        mx = max(piles)\n",
    "        cnts = [0] * (mx+1)\n",
    "        for p in piles:\n",
    "            cnts[p] += 1\n",
    "        \n",
    "        i = mx\n",
    "        while i>1:\n",
    "            while cnts[i] and k:\n",
    "                t = min(k, cnts[i])\n",
    "                cnts[i] -= t \n",
    "                cnts[i-i//2] += t\n",
    "                k -= t\n",
    "            if k == 0:\n",
    "                break\n",
    "            i -= 1\n",
    "\n",
    "        return sum(cnts[j]*j for j in range(1, i+1))\n",
    "\n",
    "        \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution():\n",
    "    def minStoneSum(self, piles, k):\n",
    "        piles = [-i for i in piles]\n",
    "        heapq.heapify(piles)\n",
    "        while k:\n",
    "            p = heapq.heappop(piles)\n",
    "            heapq.heappush(piles, p + (-p // 2))\n",
    "            k -= 1\n",
    "        return -sum(piles)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStoneSum(self, piles: List[int], k: int) -> int:\n",
    "        mx = max(piles) \n",
    "        res = [0] * (mx + 1)\n",
    "        for p in piles:\n",
    "            res[p] += 1\n",
    "        for i in range(mx, -1, -1):\n",
    "            if i == 1:\n",
    "                break\n",
    "            if res[i] < k:\n",
    "                k -= res[i]\n",
    "                tmp = i - i // 2\n",
    "                res[tmp] += res[i]\n",
    "                res[i] = 0\n",
    "            else:\n",
    "                tmp = i - i // 2\n",
    "                res[tmp] += k \n",
    "                res[i] -= k \n",
    "                break \n",
    "        return sum(i * res[i] for i in range(mx + 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def minStoneSum(self, piles: List[int], k: int) -> int:\n",
    "        n = len(piles)\n",
    "        # 生成最大堆\n",
    "        for i in range(n):\n",
    "            piles[i] = -piles[i]\n",
    "        heapq.heapify(piles)\n",
    "        for i in range(k):\n",
    "            # 单次操作：记录并弹出最大值，修改后重新添加进堆\n",
    "            tmp = heapq.heappop(piles)\n",
    "            heapq.heappush(piles, tmp + (-tmp) // 2)\n",
    "        return -sum(piles)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStoneSum(self, piles: List[int], k: int) -> int:\n",
    "        n = len(piles)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            piles[i] *= -1\n",
    "        heapify(piles)\n",
    "        while k != 0:\n",
    "            heapreplace(piles, -(-piles[0] - floor(-piles[0]/2)))\n",
    "            k-=1\n",
    "        for i in range(n):\n",
    "            ans -= piles[i]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def minStoneSum(self, piles: List[int], k: int) -> int:\n",
    "        negpiles = [-p for p in piles]\n",
    "        heapq.heapify(negpiles)\n",
    "        while k:\n",
    "            tmp = negpiles[0]-(int(negpiles[0]/2))\n",
    "            heapq.heapreplace(negpiles,tmp)\n",
    "            k -= 1\n",
    "            if k==0:\n",
    "                break\n",
    "        ans = -sum(negpiles)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStoneSum(self, piles: List[int], k: int) -> int:\n",
    "        heap = []\n",
    "        for pile in piles:  heapq.heappush(heap, -pile)\n",
    "\n",
    "        for _ in range(k):\n",
    "            cur = -heapq.heappop(heap)\n",
    "            heapq.heappush(heap, -(cur // 2 + cur % 2))\n",
    "        return -sum(heap)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStoneSum(self, piles: List[int], k: int) -> int:\n",
    "        for i in range(len(piles)):\n",
    "            piles[i] *= -1\n",
    "        heapify(piles)\n",
    "        while k:\n",
    "            # heapreplace(piles, piles[0] + (-piles[0] / 2 // 1))\n",
    "            # heapreplace(piles, piles[0] + int(-piles[0] / 2))\n",
    "            heapreplace(piles, piles[0] + (-piles[0] // 2))\n",
    "            k -= 1\n",
    "        return -sum(piles)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStoneSum(self, piles: List[int], k: int) -> int:\n",
    "        q = [-x for x in piles]\n",
    "        ret = sum(piles)\n",
    "        heapify(q)\n",
    "        while k:\n",
    "            k -= 1\n",
    "            x = -heappop(q)\n",
    "            ret -= x // 2\n",
    "            heappush(q, x // 2 - x)\n",
    "        return ret\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def minStoneSum(self, piles: List[int], k: int) -> int:\n",
    "        n = len(piles)\n",
    "        # 生成最大堆\n",
    "        for i in range(n):\n",
    "            piles[i] = -piles[i]\n",
    "        heapq.heapify(piles)\n",
    "        for i in range(k):\n",
    "            # 单次操作：记录并弹出最大值，修改后重新添加进堆\n",
    "            tmp = heapq.heappop(piles)\n",
    "            heapq.heappush(piles, tmp + (-tmp) // 2)\n",
    "        return -sum(piles)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStoneSum(self, piles: List[int], k: int) -> int:\n",
    "        h = []\n",
    "        for x in piles:\n",
    "            heappush(h, -x)\n",
    "        \n",
    "        while k:\n",
    "            k -= 1\n",
    "            x = -heappop(h)\n",
    "            heappush(h, -(x - x // 2))\n",
    "\n",
    "        return -sum(h)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def minStoneSum(self, piles: List[int], k: int) -> int:\n",
    "        piles = [-i for i in piles]\n",
    "        heapq.heapify(piles)\n",
    "        for i in range(k):\n",
    "            a = heapq.heappop(piles)\n",
    "            heapq.heappush(piles,a//2)\n",
    "        return -sum(piles)\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \"\"\"\n",
    "        n = len(piles)\n",
    "        # 生成最大堆\n",
    "        for i in range(n):\n",
    "            piles[i] = -piles[i]\n",
    "        heapq.heapify(piles)\n",
    "        for i in range(k):\n",
    "            # 单次操作：记录并弹出最大值，修改后重新添加进堆\n",
    "            tmp = heapq.heappop(piles)\n",
    "            heapq.heappush(piles, tmp // 2)\n",
    "        return -sum(piles)\n",
    "        \"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStoneSum(self, piles: List[int], k: int) -> int:\n",
    "        sm = 0\n",
    "        for i, n in enumerate(piles):\n",
    "            piles[i] = -n\n",
    "            sm += n\n",
    "        heapify(piles)\n",
    "\n",
    "        for _ in range(k):\n",
    "            n = heappop(piles)\n",
    "            n2 = n >> 1\n",
    "            sm += n - n2\n",
    "            heappush(piles, n2)\n",
    "        return sm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStoneSum(self, piles: List[int], k: int) -> int:\n",
    "        q = [-x for x in piles]\n",
    "        heapify(q)\n",
    "        while k:\n",
    "            x = heappop(q)\n",
    "            heappush(q,-(-x - (-x // 2)))\n",
    "            k -= 1\n",
    "        return -sum(q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStoneSum(self, piles: List[int], k: int) -> int:\n",
    "        for i in range (len(piles)):\n",
    "           piles[i]*=-1\n",
    "        heapify(piles)\n",
    "        while k:\n",
    "            tmp=heappop(piles)\n",
    "            heappush(piles,tmp+(-tmp)//2)\n",
    "            k-=1\n",
    "        return -sum(piles)    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStoneSum(self, piles: List[int], k: int) -> int:\n",
    "        n = len(piles)\n",
    "        # 生成最大堆\n",
    "        for i in range(n):\n",
    "            piles[i] = -piles[i]\n",
    "        heapq.heapify(piles)\n",
    "        for i in range(k):\n",
    "            # 单次操作：记录并弹出最大值，修改后重新添加进堆\n",
    "            tmp = heapq.heappop(piles)\n",
    "            heapq.heappush(piles, tmp // 2)\n",
    "        return -sum(piles)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution():\n",
    "    def minStoneSum(self, piles, k):\n",
    "        m = n = max(piles)\n",
    "        p = [0] * (n + 1)\n",
    "        for i in piles:\n",
    "            p[i] += 1\n",
    "        ans = 0\n",
    "        while k and m:\n",
    "            if p[m]: \n",
    "                t = k if k < p[m] else p[m]                                             \n",
    "                p[(m + 1) // 2] += t\n",
    "                k -= t\n",
    "                p[m] -= t\n",
    "            m -= 1\n",
    "        return sum(i * p[i] for i in range(1, n + 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minStoneSum(self, piles: List[int], k: int) -> int:\n",
    "        n = len(piles)\n",
    "        for i in range(n):\n",
    "            piles[i] = -piles[i]\n",
    "        heapq.heapify(piles)\n",
    "        for i in range(k):\n",
    "            tmp = heapq.heappop(piles)\n",
    "            heapq.heappush(piles, tmp+(-tmp)//2)\n",
    "        return -sum(piles)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStoneSum(self, piles: List[int], k: int) -> int:\n",
    "        # 贪心思路：要想让总数最小，每次操作都应该选最大的一堆进行减半。\n",
    "        # Python里负数向下除相当于正数向上除\n",
    "        import heapq\n",
    "        p = []\n",
    "        sum_ = 0\n",
    "        for x in piles:\n",
    "            heapq.heappush(p, -x)\n",
    "            sum_ += x\n",
    "        # print(p, sum_)\n",
    "        for _ in range(k):\n",
    "            tm = -heappop(p)\n",
    "            # print(\"tm\", tm)\n",
    "            sum_ -= tm\n",
    "            tm = math.ceil(tm/2)\n",
    "            # print(\"tm\", tm)\n",
    "            sum_ += tm\n",
    "            heapq.heappush(p, -tm)\n",
    "            # print(p, sum_)\n",
    "        return sum_\n",
    "\n",
    "\n",
    "        # 清风\n",
    "        # piles = [-i for i in piles]\n",
    "        # heapq.heapify(piles)\n",
    "        # while k:\n",
    "        #     p = heapq.heappop(piles)\n",
    "        #     heapq.heappush(piles, p + (-p // 2))\n",
    "        #     k -= 1\n",
    "        # return -sum(piles)\n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def minStoneSum(self, piles: List[int], k: int) -> int:\n",
    "        n = len(piles)\n",
    "        # 生成最大堆\n",
    "        for i in range(n):\n",
    "            piles[i] = -piles[i]\n",
    "        heapq.heapify(piles)\n",
    "        for i in range(k):\n",
    "            # 单次操作：记录并弹出最大值，修改后重新添加进堆\n",
    "            tmp = heapq.heappop(piles)\n",
    "            heapq.heappush(piles, tmp + (-tmp) // 2)\n",
    "        return -sum(piles)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStoneSum(self, piles: List[int], k: int) -> int:\n",
    "        h = [-x for x in piles]\n",
    "        heapify(h)\n",
    "        while h and k:\n",
    "            if -h[0] == 1: break\n",
    "            x = -heappop(h)\n",
    "            x -= x//2\n",
    "            heappush(h, -x)\n",
    "            k -= 1\n",
    "        return -sum(h)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def minStoneSum(self, piles: List[int], k: int) -> int:\n",
    "        n = len(piles)\n",
    "        # 生成最大堆\n",
    "        for i in range(n):\n",
    "            piles[i] = -piles[i]\n",
    "        heapq.heapify(piles)\n",
    "        for i in range(k):\n",
    "            # 单次操作：记录并弹出最大值，修改后重新添加进堆\n",
    "            tmp = heapq.heappop(piles)\n",
    "            heapq.heappush(piles, tmp + (-tmp) // 2)\n",
    "        return -sum(piles)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStoneSum(self, piles: List[int], k: int) -> int:\n",
    "        q = []\n",
    "        for p in piles:\n",
    "            heapq.heappush(q, -p)\n",
    "\n",
    "        while k:\n",
    "            node = -heapq.heappop(q)\n",
    "            node -= node // 2\n",
    "            heapq.heappush(q, -node)\n",
    "            k -= 1\n",
    "        return -sum(q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStoneSum(self, piles: List[int], k: int) -> int:\n",
    "        pq = [-p for p in piles]\n",
    "\n",
    "        heapq.heapify(pq)\n",
    "\n",
    "        sum_ = sum(piles)\n",
    "\n",
    "        while pq and k and sum_ != len(piles):\n",
    "            val = -heapq.heappop(pq)\n",
    "            remove = val // 2\n",
    "            sum_ -= remove\n",
    "\n",
    "            heapq.heappush(pq, -(val - remove))\n",
    "            k -= 1\n",
    "        \n",
    "        return sum_\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def minStoneSum(self, piles: List[int], k: int) -> int:\n",
    "        n = len(piles)\n",
    "        # 生成最大堆\n",
    "        for i in range(n):\n",
    "            piles[i] = -piles[i]\n",
    "        heapq.heapify(piles)\n",
    "        for i in range(k):\n",
    "            # 单次操作：记录并弹出最大值，修改后重新添加进堆\n",
    "            tmp = heapq.heappop(piles)\n",
    "            heapq.heappush(piles, tmp + (-tmp) // 2)\n",
    "        return -sum(piles)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStoneSum(self, piles: List[int], k: int) -> int:\n",
    "        import heapq\n",
    "        h=[]\n",
    "        s=sum(piles)\n",
    "        for i in piles:\n",
    "            heapq.heappush(h,-i)\n",
    "        for i in range(k):\n",
    "            x=-heapq.heappop(h)\n",
    "            s-=floor(x/2)\n",
    "            heapq.heappush(h,-(x-floor(x/2)))\n",
    "        return s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStoneSum(self, piles: List[int], k: int) -> int:\n",
    "        n = len(piles)\n",
    "        for i in range(n):\n",
    "            piles[i] = -piles[i]\n",
    "        heapify(piles)\n",
    "\n",
    "        for i in range(k):\n",
    "            x = heappop(piles)\n",
    "            x = x//2\n",
    "            heappush(piles,x)\n",
    "        return -sum(piles)\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \"\"\"\n",
    "        n = len(piles)\n",
    "        # 生成最大堆\n",
    "        for i in range(n):\n",
    "            piles[i] = -piles[i]\n",
    "        heapq.heapify(piles)\n",
    "        for i in range(k):\n",
    "            # 单次操作：记录并弹出最大值，修改后重新添加进堆\n",
    "            tmp = heapq.heappop(piles)\n",
    "            heapq.heappush(piles, tmp // 2)\n",
    "        return -sum(piles)\n",
    "        \"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStoneSum(self, piles: List[int], k: int) -> int:\n",
    "        piles = [-i for i in piles]\n",
    "        heapify(piles)\n",
    "        for i in range(k):\n",
    "            t = heappop(piles)\n",
    "            heappush(piles,t//2)\n",
    "        return -sum(piles)\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \"\"\"\n",
    "        n = len(piles)\n",
    "        # 生成最大堆\n",
    "        for i in range(n):\n",
    "            piles[i] = -piles[i]\n",
    "        heapq.heapify(piles)\n",
    "        for i in range(k):\n",
    "            # 单次操作：记录并弹出最大值，修改后重新添加进堆\n",
    "            tmp = heapq.heappop(piles)\n",
    "            heapq.heappush(piles, tmp // 2)\n",
    "        return -sum(piles)\n",
    "        \"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStoneSum(self, piles: List[int], k: int) -> int:\n",
    "        piles = [-p for p in piles]\n",
    "        ans = 0\n",
    "        heapq.heapify(piles)\n",
    "        for _ in range(k):\n",
    "            if piles[0] == -1:\n",
    "                ans += 1\n",
    "                heapq.heappop(piles)\n",
    "                if not piles:\n",
    "                    return ans \n",
    "            else:\n",
    "                heapq.heapreplace(piles, piles[0]//2)\n",
    "\n",
    "        return ans - sum(piles)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def minStoneSum(self, piles: List[int], k: int) -> int:\n",
    "        n=len(piles)\n",
    "        for i in range(n):\n",
    "            piles[i]=-piles[i]\n",
    "        heapq.heapify(piles)\n",
    "        for i in range(k):\n",
    "            tmp=heapq.heappop(piles)\n",
    "            heapq.heappush(piles,tmp+(-tmp)//2)\n",
    "        return -sum(piles)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStoneSum(self, piles: List[int], k: int) -> int:\n",
    "        sm = 0\n",
    "        for i, n in enumerate(piles):\n",
    "            piles[i] = -n\n",
    "            sm += n\n",
    "        heapify(piles)\n",
    "\n",
    "        for _ in range(k):\n",
    "            n = heapreplace(piles, piles[0] >> 1)\n",
    "            sm -= -n >> 1\n",
    "        return sm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStoneSum(self, piles: List[int], k: int) -> int:\n",
    "        heap = [-x for x in piles]\n",
    "        heapq.heapify(heap)\n",
    "        while k:\n",
    "            x = heapq.heappop(heap)\n",
    "            heapq.heappush(heap, x//2)\n",
    "            k -= 1\n",
    "        return -1 * sum(heap)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStoneSum(self, piles: List[int], k: int) -> int:\n",
    "        p=[-x for x in piles]\n",
    "        heapify(p)\n",
    "        while k :\n",
    "            heapreplace(p,p[0]+(-p[0])//2)\n",
    "            k-=1\n",
    "        return -sum(p)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution():\n",
    "    def minStoneSum(self, piles, k):\n",
    "        piles = [-i for i in piles]\n",
    "        heapq.heapify(piles)\n",
    "        while k:\n",
    "            p = heapq.heappop(piles)\n",
    "            heapq.heappush(piles, p + (-p // 2))\n",
    "            k -= 1\n",
    "        return -sum(piles)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStoneSum(self, piles: List[int], k: int) -> int:\n",
    "        res = sum(piles)\n",
    "        stone_heap = []\n",
    "        for p in piles:\n",
    "            heappush(stone_heap, -p)\n",
    "        for _ in range(k):\n",
    "            s = heappop(stone_heap)\n",
    "            half = ceil(s / 2) \n",
    "            res += half\n",
    "            heappush(stone_heap, s-half)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStoneSum(self, piles: List[int], k: int) -> int:\n",
    "        l = [-x for x in piles]\n",
    "        heapq.heapify(l)\n",
    "        for i in range(k):\n",
    "            c = -heapq.heappop(l)\n",
    "            heapq.heappush(l, -c//2)\n",
    "        return -sum(l)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStoneSum(self, piles: List[int], k: int) -> int:\n",
    "        piles = [-p for p in piles]\n",
    "        heapq.heapify(piles)\n",
    "        for _ in range(k):\n",
    "            heapq.heapreplace(piles, piles[0]//2)\n",
    "\n",
    "        return - sum(piles)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStoneSum(self, piles: List[int], k: int) -> int:\n",
    "        #最大堆\n",
    "        piles=[-i for i in piles]\n",
    "        heapq.heapify(piles)\n",
    "        for _ in range(k):\n",
    "            a=heapq.heappop(piles)\n",
    "            heapq.heappush(piles,a-ceil(a/2))\n",
    "        return -sum(piles)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStoneSum(self, piles: List[int], k: int) -> int:\n",
    "        #最大堆+贪心\n",
    "        piles=[-i for i in piles]\n",
    "        heapq.heapify(piles)\n",
    "        for _ in range(k):\n",
    "            a=heapq.heappop(piles)\n",
    "            heapq.heappush(piles,a-ceil(a/2))\n",
    "        return -sum(piles)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStoneSum(self, piles: List[int], k: int) -> int:\n",
    "        # 贪心思路：要想让总数最小，每次操作都应该选最大的一堆进行减半。\n",
    "        # import heapq\n",
    "        # p = []\n",
    "        # sum_ = 0\n",
    "        # for x in piles:\n",
    "        #     heapq.heappush(p, -x)\n",
    "        #     sum_ += x\n",
    "        # print(p, sum_)\n",
    "        # for _ in range(k):\n",
    "        #     tm = -heappop(p)\n",
    "        #     sum_ -= tm\n",
    "        #     tm = int(tm/2)\n",
    "        #     sum_ += tm\n",
    "        #     heapq.heappush(p, -tm)\n",
    "        #     print(p, sum_)\n",
    "        # return sum_\n",
    "\n",
    "\n",
    "        # 清风\n",
    "        piles = [-i for i in piles]\n",
    "        heapq.heapify(piles)\n",
    "        while k:\n",
    "            p = heapq.heappop(piles)\n",
    "            heapq.heappush(piles, p + (-p // 2))\n",
    "            k -= 1\n",
    "        return -sum(piles)\n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStoneSum(self, piles: List[int], k: int) -> int:\n",
    "        piles = [-p for p in piles]\n",
    "        heapq.heapify(piles)\n",
    "        for _ in range(k):\n",
    "            heapq.heapreplace(piles, piles[0]//2)\n",
    "\n",
    "        return - sum(piles)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStoneSum(self, piles: List[int], k: int) -> int:\n",
    "        base = sum(piles)\n",
    "        h = [-x for x in piles]\n",
    "        heapify(h)\n",
    "        s = 0\n",
    "        for _ in range(k):\n",
    "            a = -heappop(h)\n",
    "            s += a // 2\n",
    "            heappush(h, a // 2 - a)\n",
    "        return base - s "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStoneSum(self, piles: List[int], k: int) -> int:\n",
    "        from heapq import heapify,heappop, heappush\n",
    "        piles = [0-i for i in piles]\n",
    "        heapq.heapify(piles)\n",
    "        for i in range(k):\n",
    "            a = heappop(piles)\n",
    "            heappush(piles,a//2)\n",
    "        return -sum(piles)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution():\n",
    "    def minStoneSum(self, piles, k):\n",
    "        piles = [-i for i in piles]\n",
    "        heapq.heapify(piles)\n",
    "        while k:\n",
    "            p = heapq.heappop(piles)\n",
    "            heapq.heappush(piles, p + (-p // 2))\n",
    "            k -= 1\n",
    "        return -sum(piles)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStoneSum(self, piles: List[int], k: int) -> int:\n",
    "        h = [-x for x in piles]\n",
    "        heapify(h)\n",
    "        tot = sum(piles)\n",
    "        for _ in range(k):\n",
    "            x = -heappop(h)\n",
    "            tot -= x // 2\n",
    "            heappush(h, -(x - x // 2))\n",
    "        return tot"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStoneSum(self, piles: List[int], k: int) -> int:\n",
    "        heap = [*map(neg, piles)]\n",
    "        heapify(heap)\n",
    "        for _ in range(k):\n",
    "            heapreplace(heap, heap[0] >> 1)\n",
    "        return -sum(heap)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStoneSum(self, piles: List[int], k: int) -> int:\n",
    "        # res = sum(piles)\n",
    "        # stone_heap = []\n",
    "        # for p in piles:\n",
    "        #     heappush(stone_heap, -p)\n",
    "        # for _ in range(k):\n",
    "        #     s = heappop(stone_heap)\n",
    "        #     half = ceil(s / 2) \n",
    "        #     res += half\n",
    "        #     heappush(stone_heap, s-half)\n",
    "        # return res\n",
    "\n",
    "        # -----------------------------\n",
    "        piles = [-i for i in piles]\n",
    "        heapq.heapify(piles)\n",
    "        while k:\n",
    "            p = heapq.heappop(piles)\n",
    "            heapq.heappush(piles, p + (-p // 2))\n",
    "            k -= 1\n",
    "        return -sum(piles)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def minStoneSum(self, piles: List[int], k: int) -> int:\n",
    "        piles = [-i for i in piles]\n",
    "        heapq.heapify(piles)\n",
    "        for i in range(0, k):\n",
    "            num = heapq.heappop(piles)\n",
    "            heapq.heappush(piles, num - int(num / 2))\n",
    "\n",
    "        return -sum(piles)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStoneSum(self, piles: List[int], k: int) -> int:\n",
    "        n_piles = [-pile for pile in piles]\n",
    "        heapify(n_piles)\n",
    "        # print(n_piles)\n",
    "\n",
    "        for _ in range(k):\n",
    "            current = heappop(n_piles)\n",
    "            heappush(n_piles, current + floor((-current)/2))\n",
    "            # print(n_piles)\n",
    "        return -sum(n_piles)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStoneSum(self, piles: List[int], k: int) -> int:\n",
    "        piles = [-p for p in piles]\n",
    "        ans = 0\n",
    "        heapq.heapify(piles)\n",
    "        for _ in range(k):\n",
    "            p = heapq.heappop(piles)\n",
    "            if p == -1:\n",
    "                ans += 1\n",
    "                if not piles:\n",
    "                    return ans\n",
    "            else:\n",
    "                p += (-p)>>1\n",
    "                heapq.heappush(piles, p)\n",
    "\n",
    "        return ans - sum(piles)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStoneSum(self, piles: List[int], k: int) -> int:\n",
    "        piles = [-p for p in piles]\n",
    "        ans = 0\n",
    "        heapq.heapify(piles)\n",
    "        for _ in range(k):\n",
    "            p = heapq.heappop(piles)\n",
    "            if p == -1:\n",
    "                ans += 1\n",
    "                if not piles:\n",
    "                    return ans\n",
    "            else:\n",
    "                p += (-p)//2\n",
    "                heapq.heappush(piles, p)\n",
    "\n",
    "        return ans - sum(piles)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def minStoneSum(self, piles: List[int], k: int) -> int:\n",
    "        piles = SortedList(piles)\n",
    "        while k:\n",
    "            last = piles.pop(-1)\n",
    "            piles.add(last - int(last / 2))\n",
    "            k -= 1\n",
    "        return sum(piles)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
